package medium;

import data.ListNode;

import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/8/23 19:57
 */
public class No24_两两交换链表中的节点 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.add(2);
        head.add(3);
        head.add(4);
        head.add(5);
        Solution24 solution24 = new Solution24();
        ListNode res = solution24.swapPairs(head);
        System.out.println();
    }
}

class Solution24 {
    public ListNode swapPairs(ListNode head) {
        
        //递归终止条件
        if (head == null || head.next == null) {
            return head;
        }
        
        //递归....
        ListNode red = head;
        ListNode green = head.next;
        
        //处理red: 1->3->4->5
        red.next = green.next;
        
        //再处理:green接red
        green.next = red;
        
        //开始递归:传进来 3->4->5
        red.next = swapPairs(red.next);
        return green;
    }
}



    //public ListNode swapPairs(ListNode head) {
    //    ListNode headCp = new ListNode(-1);
    //    headCp.next = head;
    //    
    //    //定义双指针
    //    ListNode red = headCp;
    //    ListNode green = headCp.next;
    //    
    //    //开始操作
    //    while (red.next != null && red.next.next != null) {
    //        //1.红指针指向绿指针下一个
    //        red.next = green.next;
    //        //2.绿指针指向红指针下一个,由于红指针已经处理,故:
    //        green.next = red.next.next;
    //        //3.1 2(数字) 之间空了(红指针下一个的下一个指向绿指针)
    //        red.next.next = green;
    //
    //        //准备进行一步相同操作,移动红绿指针
    //        green = green.next;
    //        red = red.next.next;
    //    }
    //    return headCp.next;
    //}



    //public ListNode swapPairs(ListNode head) {
    //    //双指针,通过指针移动变化
    //    //???根据图写代码,如果强行脑海思考,十分容易晕眩,注意!!
    //    
    //    //定义双头,big大头,headCp 小头
    //    
    //    ListNode big = new ListNode(-2);
    //    ListNode headCp = new ListNode(-1);
    //    headCp.next = head;
    //    big.next = headCp;
    //
    //    ListNode red = big;
    //    ListNode green = headCp;
    //    ListNode yellow = headCp;
    //    
    //    //red跟green移动并处理经过的元素
    //    while (green.next != null && green.next.next != null) {
    //        red = red.next.next;
    //        green = green.next.next;
    //
    //        //交换red和green的箭头指向
    //        red.next = green.next;
    //        green.next = red;
    //        //注意这里,分析画图理解,否则十分混乱!!!!!
    //        yellow.next = green;
    //
    //
    //        //接下来,交换red和green
    //        red = green;
    //        green = green.next;
    //
    //        //为下一次做准备
    //        yellow = green;
    //    }
    //    return headCp.next;
    //}



    //public ListNode swapPairs(ListNode head) {
    //    if (head == null) {
    //        return null;
    //    }
    //    //强行硬写!!!!
    //    ListNode headCp = new ListNode(-1);
    //    headCp.next = head;
    //    //派兵过去,此时小兵处于队长位置
    //    ListNode bin = headCp;
    //    //目标获取长度
    //    int length = 0;
    //    while (bin != null && bin.next != null) {
    //        length++;
    //        bin = bin.next;
    //    }
    //    //定义数组
    //    int[] arr = new int[length];
    //    //队长叫回小兵
    //    bin = headCp;
    //    //防止头也进来数组
    //    bin = bin.next;
    //    //注意:
    //    int index = 0;
    //    while (bin != null && bin.next != null) {
    //        arr[index++] = bin.val;
    //        bin = bin.next;
    //    }
    //    //由于: bin.next != null,故需要以下代码
    //    arr[length - 1] = bin.val;
    //
    //    //开始处理数组
    //    for (int a = 0; a < length; a+=2) {
    //        if (a + 1 != length) {
    //            int tmp = arr[a];
    //            arr[a] = arr[a + 1];
    //            arr[a + 1] = tmp;
    //        }
    //    }
    //    
    //    //arr加回list
    //    ListNode res = new ListNode(-1);
    //    for (int data : arr) {
    //        addList(res, data);
    //    }
    //
    //    return res.next;
    //}
    //
    ////把data加到list最后
    //public void addList(ListNode res, int data) {
    //    while (res.next != null) {
    //        res = res.next;
    //    }
    //    res.next = new ListNode(data);
    //}

